UVa/11573 - Ocean Currents/11573.cpp

   1 /*
   2   Problem:
   3   Andrés Mejía-Posada (andmej@gmail.com)
   4 */
   5 using namespace std;
   6 #include <algorithm>
   7 #include <iostream>
   8 #include <iterator>
   9 #include <sstream>
  10 #include <fstream>
  11 #include <numeric>
  12 #include <cassert>
  13 #include <climits>
  14 #include <cstdlib>
  15 #include <cstring>
  16 #include <string>
  17 #include <cstdio>
  18 #include <vector>
  19 #include <cmath>
  20 #include <queue>
  21 #include <deque>
  22 #include <stack>
  23 #include <list>
  24 #include <map>
  25 #include <set>
  26
  27 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  28 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  29 #define D(x) cout << #x " is " << x << endl
  30
  31 char mat[1001][1001];
  32 int d[1001][1001];
  33 int rows, cols;
  34 int si, sj, ei, ej;
  35
  36 int bfs(){
  37   for (int i=0; i<rows; ++i){
  38     for (int j=0; j<cols; ++j){
  39       d[i][j] = INT_MAX >> 1;
  40     }
  41   }
  42   d[si][sj] = 0;
  43   deque<pair<int, int> > q;
  44   q.push_front(make_pair(si, sj));
  45   while (q.size()){
  46     int i = q.front().first, j = q.front().second, w = d[i][j];
  47     q.pop_front();
  48     if (w > d[i][j]) continue;
  49     if (i == ei && j == ej) return w;
  50     static const int di[] = {-1, -1, +0, +1, +1, +1, +0, -1};
  51     static const int dj[] = {+0, +1, +1, +1, +0, -1, -1, -1};
  52     for (int k=0; k<8; ++k){
  53       int ni = i + di[k], nj = j + dj[k];
  54       if (0 <= ni && ni < rows && 0 <= nj && nj < cols){
  55         int w_extra = mat[i][j] - '0' != k;
  56         if (w + w_extra < d[ni][nj]){
  57           d[ni][nj] = w + w_extra;
  58           if (w_extra){
  59             q.push_back(make_pair(ni, nj));
  60           }else{
  61             q.push_front(make_pair(ni, nj));
  62           }
  63         }
  64       }
  65     }
  66   }
  67   return -1;
  68 }
  69
  70 int main(){
  71
  72   cin >> rows >> cols;
  73   for (int i=0; i<rows; ++i){
  74     for (int j=0; j<cols; ++j){
  75       cin >> mat[i][j];
  76     }
  77   }
  78   int n;
  79   cin >> n;
  80   while (n--){
  81     cin >> si >> sj >> ei >> ej;
  82     si--, sj--, ei--, ej--;
  83     cout << bfs() << endl;
  84   }
  85   return 0;
  86 }